#include "stdafx.h"
#include "Utils.h"


void Library::Utils::ReadData( const std::string& path, std::vector<std::pair<double, double> >& points )
{
    points.clear();
    std::ifstream fileStream(path.c_str());

    size_t size = 0; 

    fileStream >> size;

    for (size_t i = 0; i < size; ++i)
    {
        std::pair<double, double> data;

        fileStream >> data.first;
        fileStream >> data.second;

        points.push_back(data);
    }

    fileStream.close();
}

void Library::Utils::CalculateDistances( const std::vector<std::pair<double, double> >& points, std::vector<std::vector<double> >& matrix )
{
    for (size_t i = 0; i < points.size(); ++i)
    {
        matrix.push_back(std::vector<double>());
        for (size_t j = 0; j < points.size(); ++j)
        {
            if (i != j)
            {
                matrix[i].push_back(DistanceBitwen(points[i], points[j]));
            }
            else
            {
                matrix[i].push_back(-1);
            }
        }
    }
}

double Library::Utils::DistanceBitwen( std::pair<double, double> first, std::pair<double, double> second )
{
    return sqrt((first.first - second.first)*(first.first - second.first) + (first.second - second.second)*(first.second - second.second));
}

void Library::Utils::PrimeAlgorithm( const std::vector<std::vector<double> >& matrix, std::vector<std::pair<int, int> >& edges )
{
    std::set<int> unusedPoints;
    std::set<int> usedPoints;

    InitializeSet(unusedPoints, matrix.size());

    edges.push_back( FindTheSmallistEdgeAndInitializeSets(matrix, usedPoints, unusedPoints));

    while (!unusedPoints.empty())
    {
        edges.push_back( FindTheBestEdgeToAdd(matrix, usedPoints, unusedPoints) );
    }
}

void Library::Utils::InitializeSet( std::set<int>& setToInitialize, int numberOfPoints )
{
    for (int i = 0; i < numberOfPoints; ++i)
    {
        setToInitialize.insert(i);
    }
}

std::pair<int, int> Library::Utils::FindTheBestEdgeToAdd( const std::vector<std::vector<double> >& matrix, std::set<int>& usedPoints, std::set<int>& unUsedPoints )
{
    double bestValue = MAXINT32;
    std::pair<int, int> result(-1, -1);

    for (std::set<int>::const_iterator i = usedPoints.begin(); usedPoints.end() != i; ++i)
    {
        for (std::vector<std::vector<double> >::size_type j = 0; j < matrix.at(*i).size(); ++j)
        {
            if (usedPoints.end() == usedPoints.find(j) && bestValue > matrix.at(*i).at(j) && *i != j)
            {
                bestValue = matrix.at(*i).at(j);
                result.first = *i;
                result.second = j;
            }
        }
    }

    assert( !((-1 == result.first) || (-1 == result.second)) );
    usedPoints.insert(result.second);
    unUsedPoints.erase( unUsedPoints.find( result.second ) );

    assert( bestValue != MAXINT32);

    return result;
}

double Library::Utils::CalculateLength( const std::vector<std::vector<double> >& matrix, const std::vector<std::pair<int, int> >& edges )
{
    double result = 0;

    for (std::vector<std::pair<int, int> >::size_type i = 0; i < edges.size(); ++i)
    {
        result += matrix.at(edges.at(i).first).at(edges.at(i).second);
    }

    assert(result >= 0);

    return result;
}

std::pair<int, int> Library::Utils::FindTheSmallistEdgeAndInitializeSets( const std::vector<std::vector<double> >& matrix, std::set<int>& usedPoints, std::set<int>& unUsedPoints )
{
    assert (usedPoints.empty());

    double bestValue = MAXINT32;
    std::pair<int, int> result(-1, -1);

    for (std::vector<std::vector<double> >::size_type i = 0; i < matrix.size(); ++i )
    {
        for (std::vector<double>::size_type j = i; j < matrix.at(i).size(); ++j)
        {
            if (bestValue > matrix.at(i).at(j) && i != j)
            {
                bestValue = matrix.at(i).at(j);
                result.first = i;
                result.second = j;
            }
        }
    }

    usedPoints.insert(result.first);
    usedPoints.insert(result.second);

    unUsedPoints.erase( unUsedPoints.find( result.first ) );
    unUsedPoints.erase( unUsedPoints.find( result.second ) );

    assert( !((-1 == result.first) || (-1 == result.second) ));
    assert( bestValue != MAXINT32);

    return result;
}

void Library::Utils::ChangeDistanceForOnePoint( const std::vector<std::pair<double, double> >& points, std::vector<std::vector<double> >& matrix, const int numberOfPoint )
{
    for (std::vector<std::vector<double> >::size_type i = 0; i < matrix.size(); ++i)
    {
        if ( i!= numberOfPoint)
        {
            matrix.at(i).at(numberOfPoint) = matrix.at(numberOfPoint).at(i) = DistanceBitwen(points.at(i), points.at(numberOfPoint));
        }
        else
        {
            assert(-1 == matrix.at(numberOfPoint).at(numberOfPoint));
        }
    }
}
